1. Field of the Invention
The present invention relates to a method of reconstructing secret information shared by a group of members, a shared secret reconstruction apparatus that can be used to carry out this method, and a secret reconstruction system that includes the shared secret reconstruction apparatus.
2. Description of the Related Art
When important secret information, such as a secret key used for encrypting information to protect its security or secret information used for authentication, is stored, there is a risk that the secret information may be lost, destroyed, or stolen. One way of preventing the loss or destruction of secret information is to make and store copies of the information, but copying the secret information increases the risk that it may be stolen. Secret sharing provides a solution to this problem. In a secret sharing scheme, a secret sharing apparatus (a processor) encrypts the original secret information and thereby generates a plurality of secret shares, which ate distributed to the participants in the secret sharing scheme. Each participant is a computing device comprising a processor and memory. When the secret information is needed, a secret reconstruction apparatus (a processor) collects shares from a necessary number of members and reconstructs (recovers) the secret information from the collected shares.
One secret sharing scheme, referred to as Shamir's method, is the (k, n) threshold secret sharing scheme described in for example, Gendai Ango (Modern Codes) by Okamoto et al., published by Sangyo Tosho. In this scheme, the secret information is encrypted as n shares, where n is an integer equal to or greater than two, in such a way that the original secret information can be recovered from any k shares, where k is an integer equal to or less than n, but nothing can be found out about the original secret information from any set of fewer than k shares.
This scheme makes use of polynomial interpolation. More specifically, the secret information is shared by using polynomials f(x) of degree k−1 having the form shown in the equation (1) below, in which S is the original secret information and R1, R2, . . . , Rk−1 are random numbers determined by the distributor.f(x)=S+R1x+R2x2+ . . . +Rk−1xk−1  (1)
If the n members to whom shares will be distributed have member IDs m1, m2, . . . , mn, the share Xmj (j=1, 2, . . . , n) for the member with ID mj (hereinafter, member ID_mj) can be calculated from the above equation (1) as shown in the following equation (2).
                              Xm          j                =                              f            ⁡                          (                              m                j                            )                                =                      S            +                                          R                1                            ⁢                              m                j                                      +                                                            R                  2                                ⁡                                  (                                      m                    j                                    )                                            2                        +            …            +                                                            R                                      k                    -                    1                                                  ⁡                                  (                                      m                    j                                    )                                                            k                -                1                                                                        (        2        )            
FIG. 1 illustrates the operation of a secret sharing operation unit 101 that carries out a secret sharing operation based on the (k, n) threshold secret sharing scheme. As shown in FIG. 1, the secret sharing operation unit 101 receives the original secret information S and the member IDs mj (j=1, 2, . . . , n) of all members to whom shares of the secret information S will be distributed, generates a polynomial f(x) equivalent to the above equation (1) on the basis of the secret information S, and then generates and outputs the shares Xmj corresponding to the member IDs mj by using the above equation (2). The output shares Xmj are secretly distributed to the members having the corresponding member IDs.
When the original secret information S is reconstructed from the shares distributed to the members, any t (k≦t≦n) members of the n members are collected, their member IDs m′1, m′2, . . . , m′t and shares Xm′1, Xm′2, . . . , Xm′t are gathered, and the secret information S is computed using the following equations (3) and (4).
                    S        =                              r            ⁢                                                  ⁢                          m              1              ′                        ⁢            X            ⁢                                                  ⁢                          m              1              ′                                +                      r            ⁢                                                  ⁢                          m              2              ′                        ⁢            X            ⁢                                                  ⁢                          m              2              ′                                +          …          +                      r            ⁢                                                  ⁢                          m              t              ′                        ⁢            X            ⁢                                                  ⁢                          m              t              ′                                                          (        3        )                                                          ⁢                  =                                    ∑                              j                =                1                            t                        ⁢                          r              ⁢                                                          ⁢                              m                j                ′                            ⁢              X              ⁢                                                          ⁢                              m                j                ′                                                                                                                  r          ⁢                                          ⁢                      m            j            ′                          =                              (                                          m                1                ′                            ×                              m                2                ′                            ×              …              ×                                                m                  t                  ′                                /                                  m                  j                  ′                                                      )                    /                      (                                          (                                                      m                    1                    ′                                    -                                      m                    j                    ′                                                  )                            ×                              (                                                      m                    2                    ′                                    -                                      m                    j                    ′                                                  )                            ×              …              ×                                                          (        4        )                                                          ⁢                              (                                          m                                  j                  -                  1                                ′                            -                              m                j                ′                                      )                    ×                      (                                          m                                  j                  +                  1                                ′                            -                              m                j                ′                                      )                    ×          …          ×                      (                                          m                t                ′                            -                              m                j                ′                                      )                          )                                                                                      ⁢                  =                                    ∏                                                i                  =                  1                                                  i                  ≠                  j                                            t                        ⁢                                          m                i                ′                            /                              (                                                      m                    i                    ′                                    -                                      m                    j                    ′                                                  )                                                                                    
When the original secret information S is reconstructed by the method described above, however, the secret information S cannot be computed without revealing the member IDs m′1, m′2, . . . , m′t and shares Xm′1, Xm′2, . . . , Xm′t of the collected members. Even if there is a trustworthy central secret reconstruction facility that carries out the reconstruction of secret information, the secret information S cannot be computed without providing that central facility with the collected member IDs m′1, m′2, . . . , m′t and shares Xm′1, Xm′2, . . . , Xm′t. That is, the conventional method is unable to compute the secret information S while the collected members remain anonymous.
If there is no such central secret reconstruction facility, the secret information S cannot be obtained unless the shares Xm′1, Xm′2, . . . , Xm′t held by the collected members are revealed to a possibly non-trustworthy party. That is, once the original secret information is reconstructed, the shares distributed to the members have been compromised and cannot be reused. It is then necessary to repeat the process of sharing the secret information.